package likou.tanxin;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/20 08:05
 */
public class _1081 {
    public static void main(String[] args) {
        System.out.println(smallestSubsequence("cdadabcc"));
    }

    public static String smallestSubsequence(String s) {
        //也可以利用,map,stack,但是速度不如直接利用数组快
        int n = s.length();
        char[] stack = new char[n];//用来模拟栈(每个字母只能唯一出现在栈中)
        int right = 0;
        int[] mLastIndex = new int[26];//用来标记每一个字母出现的最后下标,(题目中说了,字母均为小写字母)
        boolean[] mExist = new boolean[26];//用来标记其是否出现在stack中

        //遍历,将可能的字母加入栈中
        //首先统计每个字母出现的最后下标
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i) - 'a';
            mLastIndex[index] = i;
        }
        //遍历字符串
        for (int i = 0; i < n; i++) {
            int index = s.charAt(i) - 'a';
            char c = s.charAt(i);
            if (!mExist[index]) {//如果该字母没有出现在栈中
                //首先判断是否要删除前面的字母
                while (right > 0 && stack[right - 1] > c && mLastIndex[stack[right - 1] - 'a'] > i) {//栈不为空 && 栈顶元素大于当前元素(为了满足字典序要求) && 栈顶元素小标大于当前下标(意味着栈顶字母之后还会出现,可以删除)
                    mExist[stack[right - 1] - 'a'] = false;//将其存在性改成false,表示不存在在栈中
                    right--;//模拟栈,栈顶指针向后移动
                }
                //以上可能的删除操作进行完毕后,将当前没有存在在栈中的元素加入栈中
                stack[right++] = c;//加入栈中
                mExist[index] = true;//修改其存在性为true
            }
        }

        //将栈中元素变成字符串输出
        StringBuffer res = new StringBuffer(right);//用StringBuffer连接效率更高
        for (int i = 0; i < right; i++) {
            res.append(stack[i]);
        }
        return res.toString();
    }
}
